Theo Nguyên sử, Toa Đô là người của bộ tộc Trát Lạt Nhi. Toa Đô kiêu dũng thiện chiến, được tuyển vào lực lượng túc vệ, tham gia chiến đấu lập được quân công. Chức vụ quan trọng đầu tiên của Toa Đô là chức thiên hộ, chỉ huy hơn 1 nghìn quân bảo vệ Thái Xuyên.

Năm Chí Nguyên thứ 5, Aju vây Tương Dương, cử Toa Đô tuần tiễu. Toa Đô đoạt được một loạt trại của quân Tống, có trận tự mình chém được hơn 300 thủ cấp quân Tống. Năm Chí Nguyên thứ 9 (1272), quân Nguyên tấn công Phàn Thành. Toa Đô được cử làm tiên phong, lập được công và được trọng thưởng. Sau đó, trong các chiến dịch ở Giang Nam, Toa Đô tiếp tục lập nhiều quân công, được cấp trên chú ý và cất nhắc lên các chức như tham tri chính sự hành tỉnh[1] Phúc Châu, rồi tả thừa hành tỉnh Tuyền Châu.